#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<vector>
#include<queue>
#include<string>
#include<unordered_set>
using namespace std;

class Solution {
public:
    int LastRemaining_Solution(int n, int m) {
        if (n == 0 || m == 0) return -1;
        int x = 0;
        for (int i = 2; i <= n; ++i)
        {
            x = (x + m) % i;
        }
        return x;
    }

    int rotApple(vector<vector<int> >& grid) {
        int ret = 0;
        bool visited[1001][1001];
        int dir[4][2] = { {0,1},{0,-1},{1,0},{-1,0} };
        queue<pair<int, int>> qu;
        int m = grid.size(), n = grid[0].size();
        for (int i = 0; i < m; ++i)
        {
            for (int j = 0; j < n; ++j)
            {
                if (grid[i][j] == 2) qu.push({ i,j });
            }
        }
        while (qu.size())
        {
            ++ret;
            int sz = qu.size();
            while (sz--)
            {
                auto [i, j] = qu.front();
                qu.pop();
                for (int cur = 0; cur < 4; ++cur)
                {
                    auto [x, y] = dir[cur];
                    int newi = i + x, newj = j + y;
                    if (newi >= 0 && newi < m && newj >= 0 && newj < n && grid[newi][newj] == 1 && !visited[newi][newj])
                    {
                        visited[newi][newj] = true;
                        qu.push({ newi,newj });
                    }
                }
            }
        }

        for (int i = 0; i < m; ++i)
        {
            for (int j = 0; j < n; ++j)
            {
                if (grid[i][j] == 1 && !visited[i][j])
                    return -1;
            }
        }
        return ret - 1;
    }

    void dfs(vector<vector<char>>& board, int pos)
    {
        if (pos == spaces.size())
        {
            valid = true;
            return;
        }

        auto [i, j] = spaces[pos];
        for (int digit = 0; digit < 9 && !valid; ++digit)
        {
            if (!line[i][digit] && !row[j][digit] && !block[i / 3][j / 3][digit])
            {
                line[i][digit] = row[j][digit] = block[i / 3][j / 3][digit] = true;
                board[i][j] = digit + '0' + 1;
                dfs(board, pos + 1);
                line[i][digit] = row[j][digit] = block[i / 3][j / 3][digit] = false;
            }
        }
    }

    bool line[9][9];
    bool row[9][9];
    bool block[3][3][9];
    bool valid;
    vector<pair<int, int>> spaces;

    void solveSudoku(vector<vector<char>>& board) {
        memset(line, false, size(line));
        memset(row, false, size(row));
        memset(block, false, size(block));
        for (int i = 0; i < 9; ++i)
        {
            for (int j = 0; j < 9; ++j)
            {
                if (board[i][j] == '.') spaces.emplace_back(i, j);
                else {
                    int digit = board[i][j] - '0' - 1;
                    line[i][digit] = row[j][digit] = block[i / 3][j / 3][digit] = true;
                }
            }
        }
        dfs(board, 0);
    }

    struct ListNode {
        int val;
        ListNode* next;
        ListNode() : val(0), next(nullptr) {}
        ListNode(int x) : val(x), next(nullptr) {}
        ListNode(int x, ListNode* next) : val(x), next(next) {}
        
    };

    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode* head = new ListNode(-1);
        ListNode* tail = head;
        while (l1 && l2)
        {
            if (l1->val > l2->val)
            {
                tail->next = l2;
                l2 = l2->next;
            }
            else
            {
                tail->next = l1;
                l1 = l1->next;
            }
            tail = tail->next;
        }
        tail->next = l1 ? l1 : l2;
        return head->next;
    }

    ListNode* mergeKLists(vector<ListNode*>& lists) {
        ListNode* ans = nullptr;
        for (size_t i = 0; i < lists.size(); ++i)
        {
            ans = mergeTwoLists(ans, lists[i]);
        }
        return ans;
    }

    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> wordDictSet(wordDict.begin(), wordDict.end());

        int n = s.size();
        vector<bool> dp(n + 1);
        dp[0] = true;
        for (int i = 1; i <= n; ++i)
        {
            for (int j = 0; j < i; ++j)
            {
                if (dp[i] = dp[j] && wordDictSet.find(s.substr(j, i - j)) != wordDictSet.end())
                {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[n];
    }

    int maximalSquare(vector<vector<char>>& matrix) {
        int m = matrix.size(), n = matrix[0].size();
        vector<vector<int>> dp(m, vector<int>(n));
        int mx = 0;
        for (int i = 0; i < m; ++i)
        {
            for (int j = 0; j < n; ++j)
            {
                if (matrix[i][j] == '1') if (i == 0 || j == 0) dp[i][j] = 1;
                else dp[i][j] = min(dp[i - 1][j], min(dp[i - 1][j - 1], dp[i][j - 1])) + 1;
                mx = max(mx, dp[i][j] * dp[i][j]);
            }
        }
        return mx;
    }
    int takeCharacters(string s, int k) {
        int cnt[3]{};
        for (char& c : s)
        {
            ++cnt[c - 'a'];
        }
        if (cnt[0] < k || cnt[1] < k || cnt[2] < k) return -1;

        int n = s.size(), L = INT_MIN;
        for (int left = 0, right = 0; right < n; ++right)
        {
            char c = s[right] - 'a';
            --cnt[c];
            while (cnt[c] < k)
            {
                ++cnt[s[left++] - 'a'];
            }
            L = max(L, right - left + 1);
        }
        return n - L;
    }

};